#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * 扩展欧几里得算法：计算 ax + by = gcd(a,b)，返回x和y（对应Python的extend_euclid）
 * @param a: 方程系数1
 * @param b: 方程系数2
 * @param x: 输出参数，x的解
 * @param y: 输出参数，y的解
 * @return: 成功返回0，内存分配失败返回-1
 */
int extend_euclid(int a, int b, int *x, int *y) {
    // 确保 a >= b（与Python的a < b时递归交换逻辑一致）
    if (a < b) {
        int ret = extend_euclid(b, a, y, x); // 交换a/b和x/y指针
        return ret;
    }

    int *coefficients = NULL; // 存储 a//b 的系数列表
    int coeff_len = 0;        // 系数列表长度
    int coeff_cap = 4;        // 初始容量（动态扩容）

    // 初始化系数数组
    coefficients = (int *)malloc(coeff_cap * sizeof(int));
    if (coefficients == NULL) {
        fprintf(stderr, "错误：内存分配失败！\n");
        return -1;
    }

    // 循环计算系数 a//b，直到 b=0
    while (b != 0) {
        // 动态扩容（容量不足时翻倍）
        if (coeff_len >= coeff_cap) {
            coeff_cap *= 2;
            int *temp = (int *)realloc(coefficients, coeff_cap * sizeof(int));
            if (temp == NULL) {
                fprintf(stderr, "错误：内存分配失败！\n");
                free(coefficients);
                return -1;
            }
            coefficients = temp;
        }
        coefficients[coeff_len++] = a / b;
        int temp = b;
        b = a % b;
        a = temp;
    }

    // 初始化回代的x和y（对应Python的 x=1, y=0）
    *x = 1;
    *y = 0;

    // 系数列表逆序回代：x, y = y, x - y*i（Python的循环逻辑）
    for (int i = coeff_len - 1; i >= 0; i--) {
        int new_x = *y;
        int new_y = *x - (*y) * coefficients[i];
        *x = new_x;
        *y = new_y;
    }

    // 释放动态内存
    free(coefficients);
    return 0;
}

/**
 * 模逆函数：计算a在模m下的逆元（对应Python的modular_inverse）
 * @param a: 要计算逆元的数
 * @param m: 模数
 * @return: 逆元（正整数）；失败返回-1（无逆元或内存错误）
 */
int modular_inverse(int a, int m) {
    int x, y;
    int ret = extend_euclid(a, m, &x, &y);
    if (ret != 0) {
        return -1; // 内存分配失败
    }

    // 验证是否存在逆元（a和m必须互质，即ax + my = 1）
    // 注：Python代码未验证，此处补充验证逻辑（避免无逆元时返回错误结果）
    if ((a * x + m * y) != 1) {
        fprintf(stderr, "错误：%d 和 %d 不互质，无模逆！\n", a, m);
        return -1;
    }

    // 将x转换为正模m的结果（对应Python的while x < 0: x += m）
    while (x < 0) {
        x += m;
    }

    return x;
}

// 测试主函数
int main() {
    // 测试用例：对应Python的 modular_inverse(3, 7)
    int a = 3, m = 7;
    int inv = modular_inverse(a, m);

    if (inv != -1) {
        printf("%d * %d %% %d = %d\n", a, inv, m, (a * inv) % m);
        // 预期输出：3 * 5 % 7 = 1
    }

    // 额外测试用例（验证负逆元修正和无逆元场景）
    printf("\n额外测试：\n");
    // 测试1：a=5, m=14（逆元为3，5*3=15≡1 mod14）
    int a1 = 5, m1 = 14;
    int inv1 = modular_inverse(a1, m1);
    if (inv1 != -1) {
        printf("%d * %d %% %d = %d\n", a1, inv1, m1, (a1 * inv1) % m1);
    }

    // 测试2：a=4, m=6（不互质，无逆元）
    int a2 = 4, m2 = 6;
    int inv2 = modular_inverse(a2, m2);
    if (inv2 != -1) {
        printf("%d * %d %% %d = %d\n", a2, inv2, m2, (a2 * inv2) % m2);
    }

    return 0;
}